Basic structures
Generating functions
Proof techniques
Combinatorial identities
Polytopes
The order polynomial of a finite partially ordered set counts the number of ways that can be extended to a linear order of size .
By a linear extension of of size , we mean an order-preserving function from to . To see that
defines a polynomial in , first observe that any function factors as a surjection from onto some (where ), followed by an injection from to . The total number of order-preserving functions from to can therefore be calculated explicitly as
where is the number of surjective order-preserving functions from to . Hence is a polynomial of degree equal to the cardinality of .
The order polynomial of is
For example, evaluating the polynomial at confirms that there are 10 order-preserving functions from to itself.
The order polynomial of the 3-element poset
is . Evaluating at , we compute that there are 5 order-preserving functions from onto .
Let denote the lattice of lower sets in . The order polynomial of a finite poset is related to the zeta polynomial of its lattice of lower sets by the equation1
This can be seen as a consequence of the currying isomorphisms
together with the isomorphisms .
Let denote the number of strict order-preserving functions from to , that is, functions such that implies . This again defines a polynomial in , called the strict order polynomial of . The strict order polynomial of a finite poset is related to its order polynomial by the equation
where is the cardinality of . This is an example of a combinatorial reciprocity theorem in the sense of Stanley (1974).
(Notice that we are evaluating the order polynomial at a negative integer, even though the putative definition only makes sense for natural numbers . This is justified because the value of a polynomial on the natural numbers determines its value on arbitrary integers.)
As an example, the strict order polynomial of the 3-element poset defined above is . Evaluation at confirms that there is exactly one strict monotone map from to a 2-element linear order (sending both and to the first element and to the second element).
Through Möbius inversion, this equation relating the strict order polynomial to the order polynomial can be connected to the previous one relating the order polynomial to the zeta polynomial. Since the lattice of lower sets has bottom and top elements, we know that
where is the -fold convolution of the zeta function of . One can similarly work out that
where is the -fold convolution of the Möbius function of . The equation then follows formally from the fact that .
Counting the number of total linear extensions of a poset (i.e., number of linear extensions of an -element poset to a linear order of size ) is a #P-complete problem (Brightwell and Winkler 1991), and thus so is the problem of computing the leading coefficient of the order polynomial (cf. Browning, Hopkins, and Kelley 2017).
Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan. Combinatorics: The Rota Way. Cambridge, 2009.
Graham Brightwell and Peter Winkler. Counting Linear Extensions. Order 8:225-242, 1991. doi
Thomas Browning, Max Hopkins, and Zander Kelley. Doppelgangers: the Ur-Operation and Posets of Bounded Height. arXiv:1710.140407
Note that the definition we use for has an index shift from the definition that seems to be more standard in combinatorics (see the footnote at zeta polynomial), so this equation is sometimes expressed as . ↩
Last revised on June 9, 2024 at 12:19:21. See the history of this page for a list of all contributions to it.